1. Field of the Invention
The present invention relates to an apparatus and method for outputting a sequence of vectors, a data recording medium, and a carrier wave signal.
More particularly, the present invention relates to an apparatus and method for outputting a sequence of higher dimensional random vectors whose limiting distribution is expressed by an analytical density function, after associating two vector sequence generating methods by which sequences of random vectors whose limiting distribution is expressed by a known analytical density function are output, and a data recording medium storing a program which realize the above vector sequence output.
2. Description of the Related Art
Many random number generating methods utilizing recurrence formulas have been known conventionally. Many fields require random number generation. Monte-Carlo method for simulation in physics and engineering fields utilizes the random numbers.
CDMA (Code Division Multiple Access) technology for mobile phone communication assigns PN (Pseudo Noise) code to each user in order to share the limited band among many users. The PN code is generated based on the random numbers.
Moreover, public key encryption employed in telecommunication technologies utilizes the random numbers for generating public keys. Demands for such the encryption has been developing because stronger protection has been required as telecommunications such as internet has been widely used.
Traditional methods for generating the random numbers usually utilize recurrence formulas. Especially, multiplication recurrence formulas have been used widely for many years. However, such the multiplication recurrence formula also has raised problems regarding to finite periodicity. Recently, rational maps have been applied to the recurrence formulas to generate random numbers as chaos theory has been developing. The rational map is a result of the addition theorem of an elliptic function (including a trigonometric function). Demands for the random number generation by such the method which utilizes the rational map have been developing, because such the method has the following advantages.
(1) Non-cyclical random number sequence generation by which the numbers are proven to be chaotic (thus, aperiodic):
(2) Sequences of rational numbers result from rational number seeds (initial values given to the recurrence formula); and
(3) Known analytic function acts as the density function expressing random number distribution.
Known rational maps which bring the above advantages are: an Ulam-von Neumann map (equation 1), a cubic map (equation 2), a quintic map (equation 3), and the like.                               f          ⁡                      (            x            )                          =                  4          ⁢                      x            ⁡                          (                              1                -                x                            )                                                          EQUATION        ⁢                  xe2x80x83                ⁢        1                                          f          ⁡                      (            x            )                          =                              x            ⁡                          (                              3                -                                  4                  ⁢                  x                                            )                                2                                    EQUATION        ⁢                              xe2x80x83                    ⁢                      xe2x80x83                          ⁢        2                                          f          ⁡                      (            x            )                          =                              x            ⁡                          (                              5                -                                  20                  ⁢                  x                                +                                  16                  ⁢                                      x                    2                                                              )                                2                                    EQUATION        ⁢                              xe2x80x83                    ⁢                      xe2x80x83                          ⁢        3            
Regardless of the different rational maps above, the equation 4 represents a density function expressing distribution of a random number sequence x[i] which results from the following recurrence formula (where 0 less than "xgr" less than 1; "xgr" is an arbitrary initial value).
xe2x80x83x[0]="xgr"
x[i+1]=f(x[i]) (ixe2x89xa70)
                              ρ          ⁡                      (            x            )                          =                  1                      π            ⁢                                          x                ⁡                                  (                                      1                    -                    x                                    )                                                                                        EQUATION        ⁢                  xe2x80x83                ⁢        4            
A rational map with a parameter, such as a Katsura-Fukuda map, a generalized Ulam-von Neumann map (equation 5), a generalized cubic map, a generalized Chebyshev map, or the like may be applied to the recurrence formula.                                                         f              ⁡                              (                                  l                  ,                  m                  ,                  x                                )                                      =                                          4                ⁢                                  x                  ⁡                                      (                                          1                      -                      x                                        )                                                  ⁢                                  (                                      1                    -                    lx                                    )                                ⁢                                  (                                      1                    -                    mx                                    )                                                            1                -                                  Ax                  2                                +                                  Bx                  2                                +                                  Cx                  4                                                              ⁢                      
                    ⁢          where          ⁢                      
                    ⁢          A          =                      2            ⁢                          (                              l                +                m                +                                  l                  ⁢                                      xe2x80x83                                    ⁢                  m                                            )                                      ⁢                  
                ⁢                  B          =                      8            ⁢            l            ⁢                          xe2x80x83                        ⁢            m                          ⁢                  
                ⁢                  C          =                                    l              2                        +                          m              2                        -                          2              ⁢              l              ⁢                              xe2x80x83                            ⁢              m                        -                          2              ⁢                              l                2                            ⁢              m                        -                          2              ⁢              l              ⁢                              xe2x80x83                            ⁢                              m                2                                      +                                          l                2                            ⁢                              m                2                                                                        EQUATION        ⁢                  xe2x80x83                ⁢        5            
For example, if the random number sequence result from the above recurrence formula employing the generalized Ulam-von Neumann map (equation 5), limiting distribution of the resultant random number sequences is expressed by the following density function (equation 6) which includes the parameter of the generalized Ulam-von Neumann map.                                           1                                          K                ⁡                                  (                                      l                    ,                    m                                    )                                            ⁢                                                                    x                    ⁡                                          (                                              1                        -                        x                                            )                                                        ⁢                                      (                                          1                      -                      lx                                        )                                    ⁢                                      (                                          1                      -                      mx                                        )                                                                                ⁢                      
                    ⁢          where          ⁢                      
                    ⁢                      K            ⁡                          (                              l                ,                m                            )                                =                                    ∫              0              1                        ⁢                                          ⅆ                u                                                                                  (                                          1                      -                                              u                        2                                                              )                                    ⁢                                      (                                          1                      -                                              lu                        2                                                              )                                    ⁢                                      (                                          1                      -                                              mu                        2                                                              )                                                                                      ⁢                  xe2x80x83                                    EQUATION        ⁢                  xe2x80x83                ⁢        6            
The Katsura-Fukuda map is the same as the generalized Ulam-von Neumann map (equation 5) where m=0.
Unexamined Japanese Patent Application KOKAI No. H10-283344 by the inventor of the present invention discloses a technique for generating random numbers with utilizing rational maps. Theoretical backgrounds for the technique are disclosed in the following documents.
S. M. Ulam and J. von Neumann, Bull. Math. Soc. 53 (1947) pp. 1120.
R. L. Adler and T. J. Rivlin, Proc. Am. Math. Soc. 15 (1964) pp. 794.
K. Umeno, Method of constructing exactly solvable chaos, Phys. Rev.E (1997) Vol. 55 pp. 5280-5284.
Conventionally, a random number sequence (a sequence of random one-dimensional vectors) result from the above random number generating method by applying a sequence of scalars (one-dimensional vectors) to the recurrence formula as the seed.
However, such the conventional methods have the following problems.
For carrying out the Monte-Carlo method in dimension at least two, a sequence of random vectors of dimensions at least two is required. However, the conventional random number generating method generates a sequence of random numbers corresponding to a sequence of scalars (one-dimensional vectors). When the Monte-Carlo method is applied to simulation in three-dimensional space, three-value selection from head of the sequence may be required for necessary times. However, such operation causes deviation of random number distribution, thus, error convergence will be poor.
Moreover, the public key encryption requires paired integers as the random number. However, the conventional method can not perform simultaneous generation of the integers to be paired. This will make a security hole, thus, the encryption may be cracked.
Under such the circumstances, there is a great demand for an apparatus and method for outputting a sequence of vectors each of which comprises plural pairs of random numbers each being generated simultaneously as a multi-dimensional random vector, and for expressing distribution of the output vector sequence by an analytic density function.
The present invention has been made for overcome the above problems. It is an object of the present invention to provide to an apparatus and a method for outputting a sequence of higher dimensional random vectors by associating two vector sequence generating methods by which sequences of random vectors whose distribution is expressed by a known analytic density function are output, and distribution of the resultant sequence of random vectors is expressed by an analytic density function, and to provide a data recording medium storing a program which realizes the above.
To accomplish the above object, the following invention will be disclosed in accordance with the principle of the present invention.
As shown in FIG. 1, an apparatus 100 for outputting a sequence of vectors according to a first aspect of the present invention comprises a first storage 101, a first calculator 102, a second storage 103, a second calculator 104, an output 105, a first update 106, and a second update 107.
(a) the first storage 101 stores vector x of dimension at least 1;
(b) the first calculator 102 calculates vector xxe2x80x2=f(x) which utilizes a first rational vector map f to which the vector x stored in the first storage 101 is input;
(c) the second storage 102 stores vector y of dimension at least 1;
(d) the second calculator 104 calculates vector yxe2x80x2=g(x, y) which utilizes a second rational vector map g to which the vector x stored in the first storage 101 and the vector y of dimension at least 1 stored in the second storage 103 are input;
(e) the output 105 outputs vector zxe2x80x2 which is association of the vector xxe2x80x2 resulting from the first calculator 102 and the vector yxe2x80x2 resulting from the second calculator 104;
(f) the first update 106 replaces the vector x in the first storage 101 with the vector xxe2x80x2 which is the result of the first calculator 102; and
(g) the second update 107 replaces the vector y in the second storage 103 with the vector yxe2x80x2 which is the result of the second calculator 104.
Here, xe2x80x9crational vector mapxe2x80x9d means a map which converts vector of dimension at least 1 having rational number components into another vector of dimension at least 1 having rational number components.
The rational vector maps f and g may be maps based on the chaos theory (described later) or arbitrary maps applicable to a recurrence formula for random number generation. For example, a map which multiplies a giant prime number to obtain the remainder may be applicable one.
In the apparatus for outputting a sequence of vectors according to the present invention, a density function expressing limiting distribution of a sequence of vectors x, f(x), f(f(x)), f(f(f(x))), . . . which are obtained after applying 0 or more times the vector x of dimension at least 1 to the first rational vector map f, is represented by an analytic function, and
a density function expressing limiting distribution of a sequence of vectors y, g(xcex, y), g(xcex, g(xcex, y)), g(xcex, g(xcex, g(xcex, y))), . . . which are obtained after applying 0 or more times the vector y of dimension at least 1 to the second rational vector map g(xcex, xe2x80xa2) to which vector xcex of dimension at least 1 is input as a parameter, is represented by an analytic function having the parameter xcex.
As shown in FIG. 2, an apparatus 100 for outputting a sequence of vectors according to a second aspect of the present invention comprises a first storage 101, a first calculator 102, a second storage 103, a second calculator 104, an output 105, a first update 106, and a second update 107.
(a) the first storage 101 stores vector x of dimension at least 1;
(b) the first calculator 102 calculates vector xxe2x80x2=f(x) which utilizes a first rational vector map f to which the vector x stored in the first storage 101 is input;
(c) the second storage 101 stores vector y of dimension at least 1;
(d) the second calculator 104 calculates vector yxe2x80x2=g(xxe2x80x2, y) which utilizes a second rational vector map g to which the vector xxe2x80x2 resulting the first calculator 102 and the vector y having dimension at least 1 stored in the second storage 103 are input;
(e) the output 105 outputs vector zxe2x80x2 which is association of the vector xxe2x80x2 resulting from the first calculator 102 and the vector yxe2x80x2 resulting from the second calculator 104;
(f) the first update 106 replaces the vector x in the first storage 101 with the vector xxe2x80x2 which is the result of the first calculator 102; and
(g) the second update 107 replaces the vector y in the second storage 103 with the vector yxe2x80x2 which is the result of the second calculator 104.
The rational vector maps f and g may be maps based on the chaos theory (described later) or arbitrary maps applicable to a recurrence formula for random number generation. For example, a map which multiplies a giant prime number to obtain the remainder may be applicable one.
In the apparatus for outputting a sequence of vectors according to the present invention, a density function expressing limiting distribution of a sequence of vectors x, f(x), f(f(x)), f(f(f(x))), . . . which are obtained after applying 0 or more times the vector x of dimension at least one to the first rational vector map f, is represented by an analytic function, and
a density function expressing limiting distribution of a sequence of vectors y, g(xcex, y), g(xcex, g(xcex, y)), g(xcex, g(xcex, g(xcex,y))), . . . which are obtained after applying to 0 or more times the vector y of dimension at least 1 to the second rational vector map g(xcex, xe2x80xa2) to which vector xcex of dimension at least 1 is input as a parameter, is represented by an analytic function having the parameter xcex.
The first rational vector map f for the apparatus for outputting a sequence of vectors according to the present invention may be a rational map obtained by an addition theorem of the elliptic function, especially, one of Ulam-von Neumann map, cubic map, and quintic map, or one of Katsura-Fukuda map, generalized Ulam-von Neumann map, generalized cubic map and generalized Chebyshev to each of which a predetermined parameter is applied.
The second rational vector map g of the present invention may be a rational map obtained by an additional theorem of the elliptic function, especially, one of Katsura-Fukuda map, generalized Ulam-von Neumann map, generalized cubic map, and generalized Chebyshev map.
In a case where the rational maps obtained by additional theorem of the elliptic function are selected as the first and second rational vector maps f and g, a density function expressing limiting distribution of the sequence of vectors to be sequentially output by the output 105 will be obtained by a density function for a random number sequence obtained by the selected maps.
As shown in FIG. 3, an apparatus 200 for outputting a sequence of vectors according to a third aspect of the present invention comprises a generator 201, a first output 202, a second output 203, and a third output 204.
(a) the generator 201 receives vector xcex6 of dimensions at least 2, and generates vector "xgr" of dimension at least 1 and vector xcex7 of dimension at least 1;
(b) the first output 202 receives the vector "xgr" generated by the generator 201, and outputs vectors x[i] obtained by the following recurrence formula which utilizes a first rational vector map f
x[0]=xcex6
x[i+1]=f(x[i]) (where ixe2x89xa70);
(c) the second output 203 receives the vector xcex7 generated by the generator 201 and the vectors x[i] output by the first output 202, and outputs vectors y[i] obtained by the following recurrence formula which utilizes a second rational vector map g
y[0]=xcex6
y[i+1]=g(x[i], y[i]) (where ixe2x89xa70); and
(d) the third output 204 outputs vectors z[i] which is association of the vectors x[i] output by the first output 202 and the vectors y[i] output by the second output 203.
As shown in FIG. 4, an apparatus 200 for outputting a sequence of vectors according to a fourth aspect of the present invention comprises a generator 201, a first output 202, a second output 203, and a third output 204.
(a) the generator 201 receives vector xcex6 of dimensions at least 2, and generates vector "xgr" of dimension at least 1 and vector xcex7 of dimension at least 1;
(b) the first output 202 receives the vector "xgr" generated by the generator 201, and outputs vectors x[i] obtained by the following recurrence formula which utilizes a first rational vector map f
x[0]=xcex6
x[i+1]=f(x[i]) (where ixe2x89xa70);
(c) the second output 203 receives the vector xcex7 generated by the generator 201 and the vectors x[i] output by the first output 202, and outputs vectors y[i] obtained by the following recurrence formula which utilizes a second rational vector map g
y[0]=xcex7
y[i+1]=g(x[i+1], y[i]) (where ixe2x89xa70); and
(d) the third output 204 outputs vectors z[i] which is association of the vectors x[i] output by the first output 202 and the vectors y[i] output by the second output 203.
In the apparatus for outputting a sequence of vectors according to the present invention, a density function expressing limiting distribution of a sequence of vectors x, f(x), f(f(x)), f(f(f(x))), . . . which are obtained after applying 0 or more times the vector x of dimension at least one to the first rational vector map f, is represented by an analytic function, and
a density function expressing limiting distribution of a sequence of vectors y, g(xcex, y), g(xcex, g(xcex, y)), g(xcex, g(xcex, g(xcex, y))), . . . which are obtained after applying 0 or more times the vector y of dimension at least 1 to the second rational vector map g(xcex, xe2x80xa2) to which vector xcex of dimension at least 1 is input as a parameter, is represented by an analytic function having the parameter xcex.
The first rational vector map f for the apparatus for outputting a sequence of vectors according to the present invention may be a rational map obtained by an addition theorem of the elliptic function, especially, one of Ulam-von Neumann map, cubic map, and quintic map, or one of Katsura-Fukuda map, generalized Ulam-von Neumann map, generalized cubic map and generalized Chebyshev to each of which a predetermined parameter is applied.
The second rational vector map g of the present invention may be a rational map obtained by an additional theorem of the elliptic function, especially, one of Katsura-Fukuda map, generalized Ulam-von Neumann map, generalized cubic map, and generalized Chebyshev map.
In these cases, an analytic density function expressing limiting distribution of the output vector sequence is also obtained based on the rational vector maps f and g.
The first output 202 itself may act as the apparatus for outputting a sequence of vectors according to the present invention. This case is realized by the following steps.
(1) Prepare an apparatus X (for outputting a sequence of vectors) which utilizes a rational vector map f and a rational vector map g to which a parameter is input;
(2) Since the result of the apparatus X is regarded as a result of a rational vector map fxe2x80x2, another apparatus Y for outputting a further vector sequence is prepared by associating the apparatus X with a further rational vector map gxe2x80x2 to which a parameter is input. The apparatus Y can output a sequence of vectors whose dimension is higher than that of the vector sequence output by the apparatus X.
(3) Repeated preparation of apparatuses in such the manner will eventually produce an apparatus for outputting a sequence of arbitrary dimensional random vectors.
A method for outputting a sequence of vectors according to a fifth aspect of the present invention comprises:
(a) the first calculation step of calculating vector xxe2x80x2=f(x) which utilizes a first rational vector map f to which vector x of dimension at least 1 stored in a first storage is input;
(b) the second calculation step of calculating vector yxe2x80x2=g(x, y) which utilizes a second rational vector map g to which the vector x stored in the first storage and vector y of dimension at least 1 stored in a second storage are input;
(c) the output step of outputting vector zxe2x80x2 which is association of the vector xxe2x80x2 resulting from the first calculation step and the vector yxe2x80x2 resulting from the second calculation step;
(d) the first update step of updating the first storage by storing the vector xxe2x80x2 obtained by the first calculation step; and
(e) the second update step of updating the second storage by storing the vector yxe2x80x2 obtained by the second calculation step.
A method of outputting a sequence of vectors according to a sixth aspect of the present invention comprises:
(a) the first calculation step of calculating vector xxe2x80x2=f(x) which utilizes a first rational vector map f to which vector x of dimension at least 1 stored in a first storage is input;
(b) the second calculation step of calculating vector yxe2x80x2=g(xxe2x80x2, y) which utilizes a second rational vector map g to which the vector xxe2x80x2 resulting from the first calculation step and vector y of dimension at least 1 stored in a second storage are input;
(c) the output step of outputting vector zxe2x80x2 which is association of the vector xxe2x80x2 resulting from the first calculation step and the vector yxe2x80x2 resulting from the second calculation step;
(d) the first update step of updating the first storage by storing the vector xxe2x80x2 obtained by the first calculation step; and
(e) the second update step of updating the second storage by storing the vector yxe2x80x2 obtained by the second calculation step.
In the method for outputting a sequence of vectors according to the present invention, a density function expressing limiting distribution of a sequence of vectors x, f(x), f(f(x)), f(f(f(x))), . . . which are obtained after applying 0 or more times the vector x of dimension at least one to the first rational vector map f, is represented by an analytic function, and
a density function expressing limiting distribution of a sequence of vectors y, g(xcex, y), g(xcex, g(X, y)), g(xcex, g(xcex, g(xcex, y))), . . . which are obtained after applying 0 or more times the vector y of dimension at least 1 to the second rational vector map g(xcex, xe2x80xa2) to which vector xcex of dimension at least 1 is input as a parameter, is expressed by an analytic function having the parameter xcex.
The first rational vector map f for the method for outputting a sequence of vectors according to the present invention may be a rational map obtained by an addition theorem of the elliptic function, especially, one of Ulam-von Neumann map, cubic map, and quintic map, or one of Katsura-Fukuda map, generalized Ulam-von Neumann map, generalized cubic map and generalized Chebyshev to each of which a predetermined parameter is applied.
The second rational vector map g of the method for outputting a sequence of vectors according to the present invention may be a rational map obtained by an additional theorem of the elliptic function, especially, one of Katsura-Fukuda map, generalized Ulam-von Neumann map, generalized cubic map, and generalized Chebyshev map.
In this case, an analytic density function expressing distribution of the output vector sequence is also obtained based on the rational vector maps f and g.
A program which realizes the apparatus and method for outputting a sequence of vectors according to the present invention may be stored in a data recording medium such as a compact disc, a floppy disk, a hard disk, a magneto-optical disk, a digital versatile (video) disk, a magnetic tape, and a semiconductor memory apparatus.
The program may be distributed by a carrier wave signal.
A data processor having a storage, a calculator, an output apparatus, and the like, for example, a general purpose computer, a video game apparatus, a PDA (Personal Data Assistance), a mobile phone, and the like acts as the apparatus for outputting a sequence of vectors or for realizing the method, by executing the program stored in the data recording medium according to the present invention.
The data recording medium storing the program according to the present invention may be distributed or merchandised separately from the data processor apparatus.